// ALERT: 本代码中涉及的数组，是一维动态数组，。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


// FUNCTION: 定义动态数组
typedef int ElemType;

typedef struct {
	//整型指针
	ElemType *elem;
	//存储动态数组里边元素的个数
	int TableLen;
} SSTable;


// FUNCTION: 随机数生成
void ST_Init(SSTable &ST, int len) {
	// NOTE: 变量初始化
	// STEP: 多申请了一个位置,为了存哨兵
	ST.TableLen = len + 1;

	// STEP: 申请动态数组实际空间
	ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);

	// STEP: 存放赋值变量是的索引
	int i;


	// NOTE: 生成随机数
	srand(time(NULL));


	// NOTE: 将数据存储到数组中
	// HINT: 为啥这里零号位置也存放了随机了数据？是为折半查找服务的。
	for (i = 0; i < ST.TableLen; i++) {
		ST.elem[i] = rand() % 100;
	}
}


// FUNCTION: 查找结点
int Search_Seq(SSTable ST, ElemType key) {
	// NOTE: 临时变量初始化
	// STEP: 让零号元素作为哨兵
	// HINT: 哨兵的值是没有实际意义的。但引入哨兵的目的是为了当遍历到哨兵处，就应该结束遍历。
	ST.elem[0] = key;

	// STEP: 目标元素索引值
	int i;


	// NOTE: 遍历顺序表，得到目标元素索引值
	for (i = ST.TableLen - 1; ST.elem[i] != key; --i);


	// NOTE: 返回目标元素索引值
	return i;
}


// FUNCTION: 输出数组中全部元素
void ST_print(SSTable ST) {
	for (int i = 0; i < ST.TableLen; i++) {
		printf("%3d", ST.elem[i]);
	}

	printf("\n");
}


int main() {
	setbuf(stdout, NULL);

	// NOTE: Variable declaration
	// STEP: 声明动态数组
	SSTable ST;

	// STEP: 声明用于数组元素值的中间变量
	ElemType key;

	// STEP: 声明用于存储查询元素的位置
	int pos;


	// NOTE: 数组元素赋值
	ST_Init(ST, 10);
	// 验证赋值情况
	ST_print(ST);


	// NOTE: 顺序查找
	// STEP: 获取查询关键词
	printf("Perform linear search. Please input the \"key\" you want to query(Except for the sentinel first element acted as.): ");
	scanf("%d", &key);

	// STEP: 进行查询操作，并获取返回值
	pos = Search_Seq(ST, key);

	// STEP: 验证查询是否成功
	if (pos) {
		printf("Query success! Its index is %d.\n", pos);
	} else {
		printf("Query fail!\n");
	}


	return 0;
}
